package two.chapter_1.c1_3;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;


public class Ex1_3_10 {

    /**
     * 中序表达式转后序表达式
     *
     * @param args
     */
    public static void main(String[] args) {
        StdOut.println(infixToPostfix("2*3/(2-1)+3*(4-1)"));
    }

    /**
     * 中序表达式转后序表达式
     * 中序：2*3/(2-1)+3*(4-1)
     * 后序：23*21-/341-*+
     * <p>
     * 步骤：
     * <p>
     * 　1、先将中序表达式转换成字符数组
     * <p>
     * 　2、依次取得字符数组的每一个元素，直至取完
     * <p>
     * 　　　　若该元素为数字，则添加到可变字符串str中
     * <p>
     * 　　　　若该元素为左括号，则入ops栈（运算符栈）
     * <p>
     * 　　　　若该元素为右括号，则依次取出ops栈中元素，添加到str中，直至遇到左括号，左括号出栈
     * <p>
     * 　　　　若该元素为运算符：
     * <p>
     * 　　　　　　　　当栈顶为空时，或者取出元素优先级高于或等于栈顶元素时，或者栈顶为左括号时，该元素入栈
     * <p>
     * 　　　　　　　　反之，栈顶元素出栈，添加到str中，直至满足上一条语句条件
     * <p>
     * 　3、当栈顶不为空时，依次取出栈顶元素，添加到str中，直至栈顶为空
     * <p>
     * 　4、最后，得到前序表达式
     *
     * @return
     */
    private static String infixToPostfix(String infix) {

        Stack<String> stack = new LinkStack<>();
        StringBuilder sBuilder = new StringBuilder();
        String inputs[] = infix.split("");
        for (int i = 0; i < inputs.length; i++) {
            String s = inputs[i];
            switch (s) {
                case "+":
                case "-":
                case "*":
                case "/"://取出元素优先级高于或等于栈顶元素时,该元素入栈
                    if (stack.isEmpty()) {
                        stack.push(s);
                    } else {
                        String operator = stack.peek();
                        if (operator.equals("(")){
                            stack.push(s);
                        }else {
                            int cmp = compare(s, operator);
                            if (cmp == 1) {
                                stack.push(s);
                            } else {

                                sBuilder.append(stack.pop());
                                stack.push(s);
                            }
                        }
                    }
                    break;
                case "(":
                    stack.push(s);
                    break;
                case ")"://该元素为右括号，则依次取出ops栈中元素，添加到str中，直至遇到左括号，左括号出栈
                    String operator = stack.pop();
                    while (!operator.equals("(")) {
                        sBuilder.append(operator);
                        operator= stack.pop();
                    }
                    break;
                default:

                    Integer.parseInt(s);
                    sBuilder.append(s);//数字直接添加


                    break;

            }
        }
        while (!stack.isEmpty()){
            sBuilder.append(stack.pop());
        }
        return sBuilder.toString();
    }

    /**
     * @param operator
     * @param operatorThat
     * @return -1  表示 operator 小于 operatorThat  0表示相等
     */
    private static int compare(String operator, String operatorThat) {

        if (operatorThat.equals("+") || operatorThat.equals("-")) {
            if (operator.equals("*") || operator.equals("/")) {
                return 1;
            }
        }

        if (operatorThat.equals("*") || operatorThat.equals("/")) {
            if (operator.equals("+") || operator.equals("-")) {
                return -1;
            }
        }
        return 0;
    }

}



